/**
 * 97. 交错字符串
 * https://leetcode-cn.com/problems/interleaving-string/
 */
public class Solutions_97 {
    public static void main(String[] args) {
//        String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";  // output: true
//        String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc";  // output: false
        String s1 = "", s2 = "", s3 = "";  // output: true

        boolean result = isInterleave(s1, s2, s3);
        System.out.println(result);
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        char[] arr1 = s1.toCharArray(), arr2 = s2.toCharArray(), arr3 = s3.toCharArray();
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                int idx = i + j - 1;
                if (i > 0) {
                    // 从 s1 字符串中取一字符
                    dp[i][j] = dp[i - 1][j] && arr1[i - 1] == arr3[idx];
                }
                if (j > 0) {
                    // 从 s2 字符串中取一字符
                    dp[i][j] = dp[i][j] || dp[i][j - 1] && arr2[j - 1] == arr3[idx];
                }
            }
        }
//        System.out.println(Arrays.deepToString(dp));
        return dp[len1][len2];
    }
}
